Step 3: The Dijkstra's Loop

This is the core of the algorithm. We'll repeatedly pull the closest unvisited node from the `pq` and "relax" its neighbors.

Guidance for Step 3

  • Loop: Keep going as long as the priority queue `pq` is not empty.
  • Pop: Get the node `u` with the smallest cost `d` from the `pq`.
  • Optimization: If the cost `d` we just popped is *worse* than the `dist[u]` we already have, it's an old path. `continue` to the next loop.
  • "Relax" Neighbors: For each neighbor `v` (with weight `w`) of `u`:
    • Calculate `new_dist = dist[u] + w`.
    • If `new_dist` is better than `dist[v]`: Update `dist[v]`, set `parent[v] = u`, and `heappush` the new `(new_dist, v)` to the `pq`.
# 3. Run Dijkstra's Algorithm
while ______: # While the priority queue is not empty
    # Get the node with the smallest cost
    d, u = heapq.heappop(pq)

    # Optimization: skip old, worse paths
    if d > dist[u]:
        ______

    # Look at all neighbors 'v' of the current node 'u'
    for v, w in graph[u]:
        
        # Calculate the new distance to this neighbor
        new_dist = dist[u] + ______

        # If this path is shorter than any path we've seen before...
        if new_dist ______ dist[v]:
            
            # Update the distance
            dist[v] = ______
            
            # Update the parent (we got to v from u)
            parent[v] = ______
            
            # Add this new, better path to the priority queue
            heapq.heappush(pq, (______, ______))
Copied!